package zuo.from0516.other.day07;

import zuo.from0516.other.day06.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Q113:找出所有路径总和II
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，
 * 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 */
public class Code04_PathSumII {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null){
            return ans;
        }
        List<Integer> curAns = new ArrayList<>();
        curPathSum(root, targetSum, 0, ans, curAns);
        return ans;
    }
    public void curPathSum(TreeNode root, int targetSum, int curSum, List<List<Integer>> ans, List<Integer> curAns){
        if (root.left == null && root.right == null){
            if(curSum + root.value == targetSum){
                curAns.add(root.value);
                ans.add(copyList(curAns));
                curAns.remove(curAns.size() -1);
            }
            return;
        }
        curSum += root.value;
        curAns.add(root.value);
        if (root.left != null){
            curPathSum(root.left, targetSum, curSum, ans, curAns);
        }
        if (root.right != null){
            curPathSum(root.right, targetSum, curSum, ans, curAns);
        }
        curAns.remove(curAns.size() -1);

    }

    public List<Integer> copyList(List<Integer> list){
        List<Integer> copyList = new ArrayList<>();
        for(int num : list){
            copyList.add(num);
        }
        return copyList;
    }
}
